﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DesignPatternDemoCApp.AlgorithmicDemo
{

    public class QueenTest
    {

        //static void Main(string[] args)
        //{

        //    //Queen8 test = new Queen8();
        //    //test.runTest();

        //    Queen4 test2 = new Queen4();
        //    test2.runTest();

        //    Console.Read();
        //}

    }

    public class Queen8
    {
        public static int num = 0; //累计方案总数  
        public static int MAXQUEEN = 4;//皇后个数，同时也是棋盘行列总数  
        public static int[] cols = new int[MAXQUEEN]; //定义cols数组，表示8列棋子摆放情况  

        /// <summary>
        /// 最终结果,通过二维数组列表存放
        /// </summary>
        public List<string[,]> Result = new List<string[,]>();

        public void getArrangement(int n)
        {
            //遍历该列所有不合法的行，并用rows数组记录，不合法即rows[i]=true  
            bool[] rows = new bool[MAXQUEEN];
            for (int i = 0; i < n; i++)
            {
                rows[cols[i]] = true;
                int d = n - i;
                if (cols[i] - d >= 0) rows[cols[i] - d] = true;
                if (cols[i] + d <= MAXQUEEN - 1) rows[cols[i] + d] = true;

            }
            for (int i = 0; i < MAXQUEEN; i++)
            {
                //判断该行是否合法    
                if (rows[i]) continue;
                //设置当前列合法棋子所在行数  
                cols[n] = i;
                //当前列不为最后一列时  
                if (n < MAXQUEEN - 1)
                {
                    getArrangement(n + 1);
                }
                else
                {
                    //累计方案个数  
                    num++;
                    //打印棋盘信息  
                    //printChessBoard();
                    //记录当前结果
                    saveResult();
                }
            }

        }
        public void printChessBoard()
        {
            Console.WriteLine("第" + num + "种走法");
            for (int i = 0; i < MAXQUEEN; i++)
            {
                for (int j = 0; j < MAXQUEEN; j++)
                {
                    if (i == cols[j])
                    {
                        Console.Write("0 ");
                    }
                    else
                    {
                        Console.Write("+ ");
                    }
                }
                Console.WriteLine();
            }

        }

        public void saveResult()
        {
            string[,] tempArr = new string[MAXQUEEN, MAXQUEEN];
            for (int i = 0; i < MAXQUEEN; i++)
            {
                for (int j = 0; j < MAXQUEEN; j++)
                {
                    if (i == cols[j])
                    {
                        tempArr[i, j] = "0";
                    }
                    else
                    {
                        tempArr[i, j] = "+";
                    }
                }
            }
            Result.Add(tempArr);
        }

        /// <summary>
        /// 运行测试
        /// </summary>
        public void runTest()
        {
            getArrangement(0);
            Console.WriteLine(MAXQUEEN + "皇后问题有" + num + "种摆放方法。");
            for (int i = 0; i < Result.Count; i++)
            {
                Console.WriteLine($"第{i + 1}种摆法");
                //获取一维元素个数
                int rowCount = Result[i].GetLength(0);
                //获取二维元素个数
                int colCount = Result[i].GetLength(1);
                for (int rowIndex = 0; rowIndex < rowCount; rowIndex++)
                {
                    for (int colIndex = 0; colIndex < colCount; colIndex++)
                    {
                        Console.Write(Result[i][rowIndex, colIndex] + " ");
                    }
                    Console.WriteLine();
                }
                Console.WriteLine();
            }
        }

    }

    public class Queen4
    {
        public int count = 0;

        public int MAXQUEEN = 8;

        /// <summary>
        /// 存放所有最优解的集合
        /// </summary>
        public List<int[,]> Result = new List<int[,]>();

        /// <summary>
        /// 用来临时存放最优解
        /// </summary>
        int[,] TempQ = null;

        /// <summary>
        /// 判断当前行列对应位置是否合法
        /// </summary>
        /// <param name="i">行</param>
        /// <param name="j">列</param>
        /// <param name="Q">棋盘布局</param>
        /// <returns></returns>
        public bool isCorrect(int i, int j, int[,] Q)
        {
            int s, t;
            for (s = i, t = 0; t < MAXQUEEN; t++)
                if (Q[s, t] == 1 && t != j)
                    return false;//判断行
            for (t = j, s = 0; s < MAXQUEEN; s++)
                if (Q[s, t] == 1 && s != i)
                    return false;//判断列
            for (s = i - 1, t = j - 1; s >= 0 && t >= 0; s--, t--)
                if (Q[s, t] == 1)
                    return false;//判断左上方
            for (s = i + 1, t = j + 1; s < MAXQUEEN && t < MAXQUEEN; s++, t++)
                if (Q[s, t] == 1)
                    return false;//判断右下方
            for (s = i - 1, t = j + 1; s >= 0 && t < MAXQUEEN; s--, t++)
                if (Q[s, t] == 1)
                    return false;//判断右上方
            for (s = i + 1, t = j - 1; s < MAXQUEEN && t >= 0; s++, t--)
                if (Q[s, t] == 1)
                    return false;//判断左下方

            return true;//否则返回
        }

        public void Queue(int row)
        {
            //递归结束条件
            if (row >= MAXQUEEN)
            {
                //添加结果
                var tempArr = new int[MAXQUEEN, MAXQUEEN];
                for (int i = 0; i < MAXQUEEN; i++)
                {
                    for (int j = 0; j < MAXQUEEN; j++)
                    {
                        tempArr[i, j] = TempQ[i, j];
                    }
                }
                Result.Add(tempArr);
                //count++;
                //Console.WriteLine($"第{count}种走法");
                ////得到一个解，在屏幕上显示
                //for (int m = 0; m < MAXQUEEN; m++)
                //{
                //    for (int n = 0; n < MAXQUEEN; n++)
                //    {
                //        Console.Write(Q[m, n] + " ");
                //    }
                //    Console.WriteLine();
                //}
                return;
            }
            for (int col = 0; col < MAXQUEEN; col++)
            {
                TempQ[row, col] = 1;//放置皇后
                if (isCorrect(row, col, TempQ))
                {   //如果Q[i,j]可以放置皇后                    
                    Queue(row + 1);//递归深度优先搜索解空间树                    
                }
                {
                    TempQ[row, col] = 0;//这句代码就是实现回溯到上一层
                }
            }
        }

        public void runTest()
        {
            MAXQUEEN = 4;
            TempQ = new int[MAXQUEEN, MAXQUEEN];
            for (int i = 0; i < MAXQUEEN; i++)
            {
                for (int j = 0; j < MAXQUEEN; j++)
                {
                    TempQ[i, j] = 0;
                }
            }
            Queue(0);
            Console.WriteLine(MAXQUEEN + "皇后问题有" + Result.Count + "种摆放方法。");

            for (int i = 0; i < Result.Count; i++)
            {
                Console.WriteLine($"第{i + 1}种摆法");
                //获取一维元素个数
                int rowCount = Result[i].GetLength(0);
                //获取二维元素个数
                int colCount = Result[i].GetLength(1);
                for (int rowIndex = 0; rowIndex < rowCount; rowIndex++)
                {
                    for (int colIndex = 0; colIndex < colCount; colIndex++)
                    {
                        Console.Write((Result[i][rowIndex, colIndex] == 1 ? "O" : "+") + " ");
                    }
                    Console.WriteLine();
                }
            }
        }
    }
}
